#include<iostream>

using namespace std;

template<class T>
class BSTree
{
private:
    class TreeNode
    {
    public:
        T _value;
        TreeNode* _leftchild = nullptr;
        TreeNode* _rightchild = nullptr;
        TreeNode() :_value(T()) {}
        TreeNode(T value) :_value(value) {}
    };
    //拷贝函数子函数
    TreeNode* _Copy(TreeNode* root)
    {
        if (root == nullptr)return nullptr;
        TreeNode* newnode = new TreeNode(root->_value);
        newnode->_leftchild = _Copy(root->_leftchild);
        newnode->_rightchild = _Copy(root->_rightchild);
        return newnode;
    }
    //析构函数子函数
    void _Destroy(TreeNode* root)
    {
        if (root == nullptr)return;
        _Destroy(root->_leftchild);
        _Destroy(root->_rightchild);
        delete root;
    }
    //插入函数子函数
    bool _InsertR(TreeNode*& root, const T& value)
    {

        if (root == nullptr)
        {
            root = new TreeNode(value);
            return true;
        }
        if (value == root->_value)return false;
        if (value > root->_value)
        {
            return _InsertR(root->_rightchild, value);
        }
        else
        {
            return _InsertR(root->_leftchild, value);
        }
    }
    //中序遍历子函数
    void _InOrder(TreeNode* root)
    {
        if (root == nullptr)return;
        _InOrder(root->_leftchild);
        cout << root->_value << " ";
        _InOrder(root->_rightchild);
    }
public:
    //构造函数
    BSTree()
    {
        _root = nullptr;
    }

    //拷贝构造函数
    BSTree(const BSTree<T>& tree)
    {
        _root = _Copy(tree._root);
    }

    //赋值运算符重载函数
    BSTree<T>& operator=(BSTree<T> tree)
    {
        if (_root != tree._root)
        {
            _Destroy(_root);
            _root = _Copy(tree._root);
        }
        return *this;
    }

    //析构函数
    ~BSTree()
    {
        _Destroy(_root);
        _root = nullptr;
    }

    //插入函数
    // bool Insert(const T& value)
    // {
    //     TreeNode*newnode=new TreeNode(value);
    //     if(_root==nullptr)
    //     {
    //         _root=newnode;
    //         return true;
    //     }
    //     TreeNode*cur=_root;
    //     TreeNode*parent=_root;
    //     while(cur)
    //     {
    //         if(value==cur->_value)
    //         {
    //             return false;
    //         }
    //         if(value>cur->_value)
    //         {
    //             parent=cur;
    //             cur=cur->_rightchild;
    //         }else
    //         {
    //             parent=cur;
    //             cur=cur->_leftchild;
    //         }
    //     }
    //     if(value>parent->_value)
    //     {
    //         parent->_rightchild=newnode;
    //     }else
    //     {
    //         parent->_leftchild=newnode;
    //     }
    //     return true;
    // }
    bool Insert(const T& value)
    {
        return _InsertR(_root, value);
    }
    //删除函数
    bool Erase(const T& value)
    {
        if (_root == nullptr)return false;
        TreeNode* cur = _root;
        TreeNode* parent = _root;
        while (cur)
        {
            if (value > cur->_value)
            {
                parent = cur;
                cur = cur->_rightchild;
            }
            else if (value < cur->_value)
            {
                parent = cur;
                cur = cur->_leftchild;
            }
            else
            {
                if (cur->_leftchild == nullptr)
                {
                    if (cur == _root)
                    {
                        _root = _root->_rightchild;
                        delete cur;
                    }
                    else
                    {
                        if (cur == parent->_leftchild)
                        {
                            parent->_leftchild = cur->_rightchild;
                            delete cur;
                        }
                        else if (cur == parent->_rightchild)
                        {
                            parent->_rightchild = cur->_rightchild;
                            delete cur;
                        }
                    }
                }
                else if (cur->_rightchild == nullptr)
                {
                    if (cur == _root)
                    {
                        _root = _root->_rightchild;
                        delete cur;
                    }
                    else
                    {
                        if (cur == parent->_leftchild)
                        {
                            parent->_leftchild = cur->_leftchild;
                            delete cur;
                        }
                        else if (cur == parent->_rightchild)
                        {
                            parent->_rightchild = cur->_leftchild;
                            delete cur;
                        }
                    }
                }
                else
                {
                    TreeNode* pminnode = cur;
                    TreeNode* minnode = cur->_rightchild;
                    while (minnode->_leftchild)
                    {
                        pminnode = minnode;
                        minnode = minnode->_leftchild;
                    }
                    cur->_value = minnode->_value;
                    if (pminnode->_leftchild == minnode)
                    {
                        pminnode->_leftchild = minnode->_rightchild;
                    }
                    else if (pminnode->_rightchild == minnode)
                    {
                        pminnode->_rightchild = minnode->_rightchild;
                    }
                    delete minnode;
                }
                return true;
            }
        }
        return false;
    }

    //查找函数
    TreeNode* Find(const T& value)
    {
        TreeNode* cur = _root;
        while (cur)
        {
            if (value == cur->_value)
            {
                return cur;
            }
            if (value > cur->_value)
            {
                cur = cur->_rightchild;
            }
            else
            {
                cur = cur->_leftchild;
            }
        }
        return nullptr;
    }

    //中序遍历
    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }
private:
    TreeNode* _root;
};

int main()
{
    BSTree<double> tree;
    tree.Insert(4);
    tree.Insert(6);
    tree.Insert(5);
    tree.Insert(9);
    tree.Insert(7);
    tree.Insert(8);
    tree.Insert(7.5);
    tree.Insert(8.5);
    tree.Insert(10);
    tree.InOrder();


    tree.Erase(6);
    tree.InOrder();

    tree.Erase(9);
    tree.InOrder();

    tree.Erase(4);
    tree.InOrder();

    BSTree<double> treecopy(tree);
    treecopy.InOrder();

    BSTree<double> treecopy2;
    treecopy2 = treecopy;
    treecopy2.InOrder();

}

